Historically, virtual memory addressing has taken several forms. While all virtual addressing schemes map virtual addresses into real memory locations and trap virtual references to non-resident addresses, the mechanics of how these goals are accomplished differ with each of the virtual addressing forms. The three most commonly used virtual addressing schemes are segmentation, paging, and a combination of segmentation and paging. While each of these virtual addressing forms has unique characteristics, they all perform address mapping and residency testing.
In a "segmented address space," address space is regarded as a collection of named "segments," each being a linear array of addresses. "Address space" is the set of identifiers that may be used by a program to reference information. In a segmented address space, the programmer references an information item by a 2-tuple address (sd) in which s is a segment name and d is a word name within the segment identified by s. For example, the address (3,5) refers to the fifth word in the third segment. Segments are variable in length and are normally characterized by the type of information they contain (i.e. procedure segments and data segments). Each segment is described by a segment descriptor which contains information on bounds (length of segment), access privileges, location in main storage (base address of segment), and a residency flag.
Each task which is to be executed is partitioned into procedure segments and data segments and a segment descriptor table is formed to hold the segment descriptors for the task. The steps involved in forming a location address from an address space (s,d) include fetching the segment descriptor and performing a mathematical addition of the base address to the d (deflection) field, while at the same time checking the bound and other access privilege bits. If a segment s is not present in memory, a missing segment fault occurs thereby interrupting program execution until s is placed in memory.
Segmentation allows efficient organization of virtual program space. Segments are variable in length, can be structured by logical content, and have powerful protection attributes. Segmentation does, however, present some storage management problems. One problem is the need for sophisticated memory management software. Since segments are variable in length, they require complicated algorithms to position them in real memory without interfering with neighboring segments when they are needed for execution. Another problem with segmentation is real memory fragmentation. Fragmentation occurs as a result of moving segments of various lengths in and out of memory, thus leaving the memory pocketed with "holes" that are too small to hold a segment. These holes represent wasted memory. Although the holes can be collected together by moving all of the segments into one contiguous region, this process requires time and programming and represents costly operating system overhead. Thus, segmentation allows efficient organization of virtual space, but poor management of real memory.
In a "paged memory," main memory is organized into equal sized blocks of locations known as page frames, which serve as sites of residence for matching-sized blocks of virtual addresses, known as pages. The page serves as the unit both of information storage and of transfer between main and auxiliary memory. Each page frame is identified by its frame address, which is the location address of the first word in the page frame. Each page is described by a page descriptor which contains the location address of its page frame and a residency flag. Page descriptors may also contain access privilege bits although this is not common practice. Bounds or limit data is superfluous for pages because pages by definition are of fixed length.
Each task which is to be executed in the system is partitioned into pages, and a page table is formed to hold the page descriptors for a task. The processor references an information item by a two-tuple address (p,d) in which p is a page name and d is a word name (also called deflection) within the page identified by p. The pth descriptor in the page table contains the page base information. The computation that generates a memory address from the page base and deflection is trivial, amount to concatenation, since the page frames start at addresses which are integral multiples of the page size. In paging, a missing page fault occurs if p is not present in memory, thereby interrupting program execution until p is placed in memory.
Paging allows efficient management of real memory. Since virtual space is partitioned into fixed size pages that just fit into real memory page frames, it is a simple task, when a page is needed for execution, to locate a page frame and transfer the required page into it. Paging does not experience real memory fragmentation as segmentation schemes do, but some real memory waste is created by partially filled pages. This condition, called intra-page fragmentation, is not nearly as severe as real memory fragmentation. Paging does, however, present some problems with virtual program space organization. Since virtual program space is partitioned into pages and since pages are structured with physical and not software constraints, it is difficult to organize virtual space along functional lines. In addition, most paging schemes lack protection hardware. Even if protection checking is available, the lack of virtual program space organizational ability makes the protection checking difficult to use. Thus, paging allows efficient management of real memory, but poor organization of virtual space.
Some prior art systems employ a virtual addressing scheme called "segmentation and paging" that attempts to combine the virtual space organizational characteristics of segmentation with the efficient memory management characteristics of paging. The scheme is essentially two-tier addressing with each address being a three-tuple requiring two table look-ups. In segmentation and paging, the virtual address space of a task is partitioned into segments using the same software constraints followed in segmentation. Then each segment is divided into fixed size pages following the procedures used in paging. A page table is formed for each segment in the task. The page table contains page descriptors for all pages in the segment. Each page descriptor contains the location address of its page frame and a residency flag. A segment descriptor table is used to hold segment descriptors for all segments in the task. Each segment descriptor contains bounds, protection information, and a pointer to the page table of the segment. The segment descriptor table is located from a segment table origin register.
The processor references an information item by a three-tuple address (s,p,d) in which s is the segment name, p is the page name, and d is a word name (also called deflection) within page p. The page table pointer field of the sth segment descriptor in the segment descriptor table located by the segment table origin register is used to locate the page table of the segment. The pth page descriptor in the page table is used to generate the memory address by concatenation of the page frame location address field with d. Bounds and protection checks are performed using appropriate fields from the s segment descriptor. In this system, a missing page fault occurs if p is not present in memory, thereby interrupting program execution until p is placed in memory.
Segmentation with paging provides the virtual space organizational characteristics of segmentation with the efficient memory management characteristics of paging. Access privilege and bounds protection is provided without redundant storage of these items in the page descriptors. Segmentation and paging tends to be more efficient as the ratio of segment size to page size increases. This is true because, since the page is the unit of memory management, it is not necessary to have an entire segment resident at one time to start execution. All that is needed is that the page(s) in active execution be present. As a result, it is possible to have more segments in "partial" residence than in a comparable segmentation system. Intra-page fragmentation still exists in segmentation and paging because of the fixed size page constraint. Finally, segmentation and paging tend to require a wide characteristic address word because segment length must be large enough to accommodate tasks with large program modules while at the same time the number of segments available to a task must be large enough to accommodate programs with large numbers of (probably small) procedure and data modules.
With the foregoing background in mind, the present invention was developed to provide a virtual address translator which would incorporate the virtual program space organizational ability provided by segmentation. This virtual program space organizational ability is based on the assumption that procedure and data modules of any size can be mapped into segments. This assumption, however, is not really true. Conceptually, segments can be of any size up to the maximum allowable by the characteristic address word size of the computer (i.e., the sum of the s field width and the d field width for a segmented machine). In actual practice, however, this is not possible. There is a tradeoff involved between maximum segment size and the number of segments available to a task. For a given characteristic address word size, increasing the maximum segment size decreases the number of segments available to a task. The traditional solution to having both a large maximum segment size and a large number of segments available to a task, has been to provide very large characteristic address word sizes in computers using the segmentation scheme.
The intent of the traditional solution is to provide a reasonable number of segments while also providing a maximum segment size large enough so that occurrences of program modules which exceed this size are exceedingly rare. As an example, one system of the prior art which uses segmentation and paging, has a characteristic address word size of 24 bits. The number of segments available to a task is 256 and the maximum length of each segment is 65K words. However, it was intended that the present invention be utilized with computers having a characteristic address word size on the order of 16 bits. Furthermore, one of the design constraints placed on the present invention was that it should function as a separate module allowing computers normally operating in an absolute address environment to operate in a virtual address environment with only a minimum modification. Therefore, in order for the present invention to use some form of segmentation, it was necessary to devise a different solution to the maximum segment size problem.
At this point it is helpful to examine the basic segmentation premise that says that program modules, regardless of size, must be mapped into single segments. This constraint is not really necessary to achieve efficient virtual space organization. A system was devised that maps each program module into a number of "fixed length segments" and one "variable length segment." It is assumed that the "variable length segment" is always smaller in size than the "fixed length segments." The number of "fixed length segments" needed to map a program module is determined by the program module length. If the program module length is less than the size of the "fixed length segment", then only a "variable length segment" is needed to complete the mapping process. "Fixed length segments" and "variable length segments" are both defined by segment descriptors having the same structure. The only difference between them is that segment descriptors for "fixed length segments" have bounds fields set equal to the maximum segment size and segment descriptors for "variable length segments" have bounds fields set equal to values less than the maximum segment size. If both the "fixed length segments" and "variable length segments" have all the characteristics associated with segments of the segmentation scheme described above, then the use of fixed length and variable length segments constitutes a segmentation scheme that solves the maximum segment length problem without having to increase the address word size of the computer. The only additional cost of this segmentation scheme over traditional segmentation is the need to store program module access and protection information redundantly in all of the fixed lengths and variable length segment descriptors.
It should be noted that in the present invention the segments are not intended to be large enough to hold an entire program module. Therefore the segments will hereinafter be referred to as subsegments and the virtual addresssing scheme will be referred to as subsegmentation. Subsegments have all the characteristics of segments except that they generally will be smaller than the anticipated average size of program modules that will be run on the associated computers. This fact lets subsegments assume some of the efficient memory management attributes that pages have in segmentation and paging schemes. If subsegments tend to be small in relation to the average size of program modules, then it is not necessary to have all of the subsegments of a program module resident in real memory at one time in order to execute the program module. All that is required is that the subsegment(s) in active execution be present. As a result, it is possible to have more program modules in "partial residence" than would be the case in a comparable segmentation scheme.
Subsegmentation has very interesting ramifications to automatic storage management when compared to automatic storage management associated with segmentation or paging. A subsegment scheme has two units of memory management -- the fixed length subsegment and the variable length subsegment. As a result, real memory can be managed in two regions: the fixed length region and the variable length region. This means that with subsegmentation it is possible to realize the efficient memory management attributes of paging for at least a portion of real memory, while at the same time never experiencing the intra-page fragmentation problems associated with paging. Although real memory fragmentation can still occur with subsegmentation schemes in the variable length region of memory, the solution to this problem (i.e., collecting the variable sized segments into one contiguous area of the variable length region) is far less costly than the solution to real memory fragmentation as experienced in segmentation schemes because, with segmentation, collection must be performed over all of the real memory.
One of the difficulties encountered in virtual memory systems is the problem of task switching. If a virtual memory computing system is multi-programmed, then portions of several tasks will be resident in memory at any one time. Since most of the virtual memory systems built today provide only one "task defining register", this register must be constantly loaded and changed as tasks are switched. For paging systems, this "task defining register" is called the page table origin register and it is used to hold a pointer to the page table of the task currently in active execution. Each time a task is switched in a paging system, the page table origin register has to be loaded with a pointer to the new task's page table. For segmentation or segmentation and paging systems, the "task defining register" is called the segment table origin register and it is used to hold the pointer to the segment descriptor table of the task currently in active execution. Each time a task is switched in the segmentation or segmentation and paging system, the segment table origin register must be loaded with a pointer to the new task's segment descriptor table.
In accordance with one aspect of the present invention, the task switching capability is improved as compared to the above systems by means of a task address table. Whenever a task is created in the VAT-equipped system, it is assigned a task number and a task segment descriptor by the executive. The task descriptor segment contains cells into which the executive stores the task subsegment descriptors. The task descriptor segment is located in main memory at a base address which is entered into the task associated cell within the task address table The task address table is a 256 word memory located in the virtual address translator that serves as "task defining registers" for the 256 tasks that can be active at any one time in a translator-equipped system. Task address table cell 0 contains a pointer to the task descriptor segment for task 0, cell 1 contains a pointer to the task descriptor segment for task 1, and so on. Each virtual address sent to the virtual address translator from the computer has an eight-bit preamble which is the task name for the program currently executing in the computer. This task name locates the correct "task defining register" within the task address table. Once the correct "task defining register" has been found, address mapping proceeds just as in segmentation.
The use of task names in the virtual address allows simple and efficient task switching. All that is necessary in the way of task switching overhead is that the associated task address table entry be initiated when a task is first entered into the system. The actual task switching is then effected by simply changing the contents of the task name registers in the computer. The computer associated with the virtual address translator is provided with two eight-bit task registers. One of these task registers is called the "instruction task register" and it holds the name of the task currently in active execution. The other task register is called the "data task register" and it holds the task name of the data subsegment currently being processed. The instruction task register supplies the task name to virtual addresses for all instruction references to memory and the data task register supplies the task name to virtual addresses for all operand references. This use of two task registers allows one task to process data from other tasks.
In prior-art systems, even those employing virtual addressing, it has been conventional to utilize absolute addressing techniques for input and output (I/O) operations. The use of multiple task names makes it possible to handle all I/O addresses in the same fashion as central processor (CP) addresses. The effect of this implementation is to extend all the attributes of virtual memory to I/O. These include relocatability, access and overflow checking, and simplification of overlay by the double program name concept. The simple extension to I/O of all these capabilities is logical except for the traditional read-write-execute transaction privilege bits. There is no automatic correspondence between the transaction privileges which are appropriate for I/O as opposed to CP. In accordance with the present invention, each subsegment includes separate read-write-execute bits for I/O which are distinct from those for CP. The CP provides a discrete signal to the VAT which declares the virtual address to be I/O, and this causes the transaction privileges of the I/O to be used in the validity checks.
Virtual I/O addressing also allows I/O to load non-contiguous areas of memory in a single buffer transaction, which helps to allow small blocks for efficiency in memory management, and larger blocks for auxiliary store efficiency.